package demo10;

import java.io.BufferedWriter;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;

public class FindDuplicateNumber {
    public  FindDuplicateNumberWithBitVector createFindDuplicateNumberWithBitVector(int offset,int max){
        return new FindDuplicateNumberWithBitVector(offset,max);
    }
    public static void main(String[] args) throws IOException {
        int offset = 2 * 1000;
        int max = 32 * 1000;

        FindDuplicateNumber findDuplicateNumber = new FindDuplicateNumber();
        FindDuplicateNumber.FindDuplicateNumberWithBitVector bitVector = findDuplicateNumber.createFindDuplicateNumberWithBitVector(offset,max );

        int length = (max/offset);
        int[] maxList =new int[length];
        for (int i=0;i<length;i++){
            maxList[i]=offset * i;
        }
        bitVector.initAndFind(maxList);


    }
    public class FindDuplicateNumberWithBitVector{
        int offset = 8  ;
        int max = 32 ;
        byte[] bitfield = null;
        public FindDuplicateNumberWithBitVector(){
        }
        public FindDuplicateNumberWithBitVector(int offset,int max){
            this.offset=offset;
            this.max=max;
            this.bitfield=new byte[max / 8 + 1 ];
        }

        public void writeFile() throws IOException {
            Path sourcePath = Paths.get(
                    "F:/integration/basic/SpringWithGradle-gitee/Algorithm/simple-demo/src/test/resources/inputForDuplicate.txt"
            );

            BufferedWriter bufferedWriter = Files.newBufferedWriter(sourcePath, StandardOpenOption.CREATE,StandardOpenOption.WRITE);
            for (int i = 0; i < 32 * 1000; i++) {
                bufferedWriter.write(i+"");
                bufferedWriter.newLine();
            }
            bufferedWriter.flush();;
            bufferedWriter.close();

        }
        /**  could you   using merge sort need 32 KB < 4KB no!
         *    int[] ints = new int[32 * 1000 ];
         *   can using the hashSet ,but have no room to store this ,i only  have 4 * 000 => 4KB
         *
         *    4KB , can divide 32000 into multiple  range  like  [0~2000) [2000~4000) ..
         *    multiple foreach ,
         *    you can using bit vector . save the space .
         *   bitfield[0] & (1<<i) !=0 , indicate bitfield contains the element ,
         *    // 0~8
         *    bitfield[0]
         *    | (1<<i) ==0 ,    is same as BigSearch
         * when foreach and add the array , need ensure is duplicate ?
         */
        public void initAndFind(int[] max) throws IOException {
            // inputForDuplicate
            Path sourcePath = Paths.get(
                    "F:/integration/basic/SpringWithGradle-gitee/Algorithm/simple-demo/src/test/resources/inputForDuplicate.txt"
            );
            assert  sourcePath.toFile().exists();
            for (int j : max) {
                // [1,8]   => 1~7 ,0
                // 0 , 8
                int start = j +1  ;
                int end = j + offset   ;
                Files.lines(sourcePath).forEach(line -> {
                    int i = Integer.valueOf(line);
                    searchLoop(i,start,end);
                });
            }

        }
        public void searchLoop(int i, int start,int end){
            if (start <= i && i <=end){
                int remainder = i % 8;
                if((bitfield[i/8] & (1 << remainder))!=0){
                    System.out.println("duplicat int is : " + (i));
                }
                bitfield[i/8] |= 1 << (i % 8);
            }

        }

    }

}
